package wildcard

const (
	normal      = iota
	all         // *
	any         // ?
	setSymbol   // []
	rangeSymbol // [a-b]
	negSymbol   // [^a]
)

type item struct {
	char     byte
	set      map[byte]bool
	typeCode int
}

func (item *item) contains(c byte) bool {
	if item.typeCode == setSymbol {
		return item.set[c]
	} else if item.typeCode == rangeSymbol {
		if item.set[c] {
			return true
		}
		var (
			min uint8 = 255
			max uint8 = 0
		)
		for k := range item.set {
			if min > k {
				min = k
			}
			if max < k {
				max = k
			}
		}
		return c <= max && c >= min
	} else {
		return !item.set[c]
	}
}

// Pattern represents a wildcard pattern
type Pattern struct {
	items []*item
}

// CompilePattern convert wildcard string to Pattern
// 总觉得这个算法有问题啊
// 好吧 redis好像只支持普通简单的模糊匹配  set匹配也只是简单的模式 像[a-zA-Z]应该是不行的
func CompilePattern(src string) *Pattern {
	items := make([]*item, 0)
	escape := false
	inSet := false
	var set map[byte]bool
	for _, v := range src {
		c := byte(v)
		if escape {
			items = append(items, &item{typeCode: normal, char: c})
			escape = false
		} else if c == '*' {
			items = append(items, &item{typeCode: all})
		} else if c == '?' {
			items = append(items, &item{typeCode: any})
		} else if c == '\\' {
			escape = true
		} else if c == '[' {
			if !inSet {
				inSet = true
				set = make(map[byte]bool)
			} else {
				set[c] = true
			}
		} else if c == ']' {
			if inSet {
				inSet = false
				typeCode := setSymbol
				if set['-'] {
					typeCode = rangeSymbol
					delete(set, '-')
				}
				if set['^'] {
					typeCode = negSymbol
					delete(set, '^')
				}
				items = append(items, &item{typeCode: typeCode, set: set})
			} else {
				items = append(items, &item{typeCode: normal, char: c})
			}
		} else {
			if inSet {
				set[c] = true
			} else {
				items = append(items, &item{typeCode: normal, char: c})
			}
		}
	}
	return &Pattern{items: items}
}

// IsMatch returns whether the given string matches pattern
func (p *Pattern) IsMatch(s string) bool {
	if len(p.items) == 0 {
		return len(s) == 0
	}
	m := len(s)
	n := len(p.items)
	dp := make([][]bool, m+1)
	for i := 0; i <= m; i++ {
		dp[i] = make([]bool, n+1)
	}
	dp[0][0] = true
	for j := 1; j <= n; j++ {
		dp[0][j] = dp[0][j-1] && p.items[j-1].typeCode == all
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if p.items[j-1].typeCode == all {
				dp[i][j] = dp[i-1][j] || dp[i][j-1]
			} else {
				dp[i][j] = dp[i-1][j-1] && (p.items[j-1].typeCode == any || (p.items[j-1].typeCode == normal && s[i-1] == p.items[j-1].char) || (p.items[j-1].typeCode >= setSymbol && p.items[j-1].contains(s[i-1])))
			}
		}
	}
	return dp[m][n]
}
